/*

dp[u][0]: 只考虑以 u 为根的子树，在子树内的城市中不建立任何军营的方案数
dp[u][1]: 只考虑以 u 为根的子树，在子树内的城市中至少建立一个军营的方案数。
dp[u][0] = 1

看守桥 (u, v): 桥是安全的。u 这边的军营状况和 v 那边的军营状况可以独立。
u 无军营，v 有军营：dp[u][0] * dp[v][1]
u 有军营，v 无军营：dp[u][1] * dp[v][0]
u 有军营，v 有军营：dp[u][1] * dp[v][1]
不看守桥 (u, v): 桥是不安全的。所有军营必须在同一侧。
要么所有军营都在 v 的子树中 (u 这边无军营)：dp[u][0] * dp[v][1]
要么所有军营都在 v 的子树外 (v 那边无军营)：dp[u][1] * dp[v][0]

*/



int main(){
    
}